package com.zjsru.oneDay202212;

/**
 * @Author: CookLee
 * @Date: 2022/12/19
 *  寻找图中是否存在路径
 *
 * 输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
 * 输出：true
 * 解释：存在由顶点 0 到顶点 2 的路径:
 * - 0 → 1 → 2
 * - 0 → 2
 *
 * 输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
 * 输出：false
 * 解释：不存在由顶点 0 到顶点 5 的路径.
 */
public class ValidPath {
    
    /**
     * 并查集
     */
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        unionFind uf = new unionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.isConnected(source, destination);
    }
    
    class unionFind {
        
        int[] parent;
        
        public unionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        //首尾点校验
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
        
        private int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            return parent[x] = find(parent[x]);
        }
        
        public void union(int p, int q) {
            int pRoot = find(p), qRoot = find(q);
            if (pRoot != qRoot) {
                parent[qRoot] = pRoot;
            }
        }
    }
    
    public static void main(String[] args) {
        ValidPath validPath = new ValidPath();
        int n = 3;
        int[][] edged = new int[][] {{0, 1}, {1, 2}, {2, 0}};
        int source = 0;
        int destination = 2;
        System.out.println(validPath.validPath(n, edged, source, destination));
    }
}
